Libris Britannia 4/science library(b).zip/science library(b)/HAM_RAD/0088.ZIP/WB6UUT.TXT

Text File | 1985-06-15 | 21KB | 379 lines

.          A Proposed Level 3 Routing Algorithm for
.                     Amateur Packet Radio
.
.                   By Lynn W. Taylor, WB6UUT
.
.Yea, from the table of my memory
.I'll wipe away all trivial fond records.
.                        -- Hamlet (Act I, Scene 5, line 98)
.
.    According  to the ISO Open Systems Interconnect  model,  the
network  controllers are responsible for the first three  of  the
seven  protocol layers in a packet switched network.     Layer 1,
the  Physical level,  is responsible for the physical aspects  of
communication (radios,  modems,  HDLC, baud rates).  Layer 2, the
Data  Link level,  is responsible for taking the physical  medium
and  making  it error-free,  and dividing it up among the  users.
The  third layer,  called the Network,  or Communications  Subnet
level  determines the host-subnet interface and how  packets  are
routed  in the subnet.   Levels 4 through 7 deal with issues that
are beyond the scope of this paper.
.
.    Routing   is  one  of  the  key  issues  when   defining   a
Communications  Subnet  Level  protocol.    The  various  routing
algorithms can be divided into two categories, centralized (where
some  central station must know or discover the network topology,
and  serve  as  a clearinghouse for  routing)  and  decentralized
(where  each TNC can handle at least part of the  routing  task).
Centralized  algorithms  must  be designed to  recover  when  the
master  station crashes,  and each station must know how to reach
the router itself.  Decentralized algorithms require each station
to  know  how to pass traffic to other stations in  the  net;  to
accomplish  this,  the TNC needs to find out something about  the
nework topology.
.
.    I  am going to discuss two specific routing algorithms,  the
advantages  and drawbacks of each,  and why I believe  we  should
select  a decentralized algorithm for Amateur use.   None of this
material is original, and most is discussed at some length in the
computer  science literature.   Some of the combinations of  this
information are new,  particularly as they relate to the specific
problems of Amateur usage.
.
.    The  first  algorithm has a couple of  advantages,  and  one
major disadvantage.   This algorithm does not require any special
knowlege of the network topology,  other than a list of  stations
that the TNC can hear.   When the TNC receives a packet addressed
to someone other than itself,  it simply passes it on to everyone
it  can  hear  except  the station  it  received  it  from.   The
algorithm is appropriately called Flooding.
.
.    Flooding is easy to understand,  and easy to implement.  The
problem comes when the load on the network increases.  Since each
packet  will pass through every single node in the  network,  and
many of them more than once,  the amount of traffic generated  by
simply saying "Hi" can be staggering.   Also, steps must be taken
to prevent packets from looping forever through the network.  The
simplest  case of this is a 4 station net (A,  B,  C and D) where
all 4 stations can hear each other.  If A originates a packet for
D,  it passes it to all 3 stations it can hear.   B passes it  to
both C and D,  where D accepts it, and C passes it to A and D.  D
has  already  got the packet and ignores the duplicate,  while  A
passes  it to B and D.   Again,  D discards it,  and B passes  it
around.   At  the same time,  packets are flowing in the opposite
direction around the same loop.   While this simple case could be
easily  fixed,  it  becomes more complex in a  larger  net.   One
solution  is to limit the life of any given packet to  a  certain
number  of  hops,  but this still generates a lot of  unnecessary
traffic.
.
.    A  better algorithm would require  each TNC to have a  table
giving the address of each node in the network,  some measure  of
the distance to that station, and the address of the next station
along a path to that station.   A hypothetical 5 station net, and
each node's tables is shown below:
.
.               A <---> B <---> C <---> D <---> E
.
.             B 1 B   A 1 A   A 2 B   A 3 C   A 4 D
.             C 2 B   C 1 C   B 1 B   B 2 C   B 3 D
.             D 3 B   D 2 C   D 1 D   C 1 C   C 2 D
.             E 4 B   E 3 C   E 2 D   E 1 E   D 1 D
.
.    In  this  example,  the available communications  paths  are
shown  by  arrows (i.e.  A cannot communicate directly  with  C).
Note that each station knows how far away all the other  stations
are,  and  who is the next station in the chain.   If A wants  to
talk to D,  A knows to pass traffic to D, and it will take 3 hops
to get there.  It is up to B to know who to pass these packets on
to.
.
.    The  problem  with  this method is easy to see  -- where  do
these tables come from?   In the proposed WestNet protocol, which
defines a long-haul network for linking geographically  seperated
LANs,  a  similar  algorithm  is  used which  assumes  all  nodes
internal  to  the network will stay on.   In  other  words,  this
network is static (because all the nodes are dedicated devices to
be  installed  on mountaintops).   In a local  network,  stations
(nodes) tend to appear and disappear frequently.
.
.    In  a dynamic network,  the answer to the question  must  be
"from  the  network  itself."   This  further  divides  into  two
problems:  how does a new station get it's initial table, and how
do  we  make  sure the table each node has is  up  to  date.   To
clarify this problem, lets add station F to our earlier network:
.
.               A <---> B <---> C <---> D <---> E
.               ^                               ^
.               |                               |
.                -------------> F <-------------
.
.    In this example,  A should now pass traffic for E through F,
while  traffic  for  D  can follow it's  previous  route,  or  as
efficiently  through  E and F.   If all stations listen  for  new
stations on the air,  and F comes on and sends an "I'm here"  (or
CQ) packet,  A and  E can detect F's presence,  connect with F to
make sure they can communicate,  and pass copies of their routing
tables.   By taking the best information from both tables,  F can
build it's initial table:
.
.                             A 1 A
.                             B 2 A
.                             C 3 E
.                             D 2 E
.                             E 1 E
.
.    There are two equally good paths from F to C (through E  and
D, and through A and B), F selects these at random.
.
.    Also,  the  rest  of the net need to be told about  the  new
network  topology.    First,  A  (and  simultaneously,  E)  tells
everyone  it can hear that F is one hop away from it.   B  checks
it's routing tables,  decides that this is good news,  and passes
the  news  along  to everyone it can  hear,  etc.   This  is  the
flooding  algorithm again,  with a twist;  stations only pass  on
good  news,  so if a station already has a path of length  N,  it
only  passes on news of a path of N-1.   In other words,  when  B
announces to A and C that "I'm 2 hops from F", C is glad to hear,
while A could care less, since A is only 1 from F, while C didn't
even know F existed.   C will wind picking the first path to F it
hears about,  since it has 2 paths of length 3 to F.   This  also
means  that C might use a different path to F than F would use to
C; this does not matter since each have the same length.
.
.    F  would  also  pass on the news of  it's  complete  routing
table,  since the whole table is news to it.   This way, A learns
of the new path through F to E and E learns about it's new paths.
The new tables would look like this:
.
.             B 1 B   A 1 A   A 2 B   A 3 A   A 2 F
.             C 2 B   C 1 C   B 1 B   B 2 C   B 3 D
.             D 3 B   D 2 C   D 1 D   C 1 C   C 2 D
.             E 2 F   E 3 C   E 2 D   E 1 E   D 1 D
.             F 1 F   F 2 A   F 3 A   F 2 E   F 1 F
.
.               A <---> B <---> C <---> D <---> E
.               ^                               ^
.               |                               |
.                -------------> F <-------------
.
.                             A 1 A
.                             B 2 A
.                             C 3 E
.                             D 2 E
.                             E 1 E
.
.    Adding  a  node  to the network is  easy  compared  to  what
happens when a node leaves the net.   Having a node  tell the net
it's leaving is impractical, because that node may not be able to
tell  the net because of hardware failures,  power  failures,  or
propogation changes.   One solution would be for a node to report
to  the  rest of the net that node X is unreachable  whenever  it
can't  pass  traffic  on to X.   This bad news  would  be  passed
through the net until it reaches X,  which would then tell  those
stations  it  can still reach that it is indeed still  reachable,
generating a new set of entries in the network tables.
.
.    As an example,  A is passing traffic for E through F when  F
goes  off  the  air.   A,  realizing that it can't  pass  traffic
through  F announces to B that E is unreachable.   B passes  this
news  to C,  who passes on to D,  and eventually to E.   At  this
point, E has been erased from everyone's routing tables.  E would
then  tell D "I'm still accessable",  D reports to C that  "E  is
still  1 hop from me",  and the good news passes through the  net
(and contradicts any bad news still circulating).   A may now use
the longer path through B, C and D, and the network has recovered
from the loss of the path to E through F.
.
.    The  problem  of  updating the routing tables  is  the  most
serious drawback of this algorithm,  and I am not suggesting that
the  method  I  have explained above is the  best.   In  Computer
Networks  by  Andrew Tannenbaum,  he points out that  "good  news
travels fast" while bad news may take awhile to propogate through
the network,  especially where looped paths exist.  By completely
eliminating  a station from the network tables  and  re-inserting
it, many of these kinds of problems may be avoided.
.
.    I  have  explained  two  decentralized  routing  algorithms.
These  algorithms allow the nodes themselves,  on an equal basis,
to decide how to route data in the net, and dynamically alter the
routing  when  the network composition  changes.   What  are  the
problems involved in a centralized algorithm?
.
.    Centralized  algorithms  require  a single station  to  have
complete knowlege of the network.  To do this, the master station
must probe the network,  and pass on it's discoveries to the rest
of the net.  The master must either be a unique station type, or,
in  a homogeneous network,  a station must be  selected to be the
master.  A new station, when it comes on the air, must be able to
tell the master it is on,  and, if it can't reach a master, would
most  likely  become one.   Problems exist,  in the case  of  two
networks "growing" together (more than one master),  and when the
master  fails.   Depending on the implementation,  a network  may
continue  to operate without the master based on old  information
the master distributed,  or collapse when the master  disappears.
Either solution would be undesirable.
.
.    I  have shown that a properly designed decentralized  system
will  not  suffer  unduly from the loss of  any  single  critical
station,  and  recover from the loss of any node in a  reasonable
manner.    Centralized   systems  rely  on  the  master   station
discovering the complete network topology, finding changes due to
propogation,  etc.  and  distributing this info.   Since  Amateur
packet nets are very dynamic, it is probable that the master will
be  lost,  causing the net to crash,  or continue on without  any
direction.
.
.    While  I  feel  the  decentralized  approach  is  best,  the
possibility  of  reasonable mechanisms for operating  centralized
networks,  hybrid networks,  rings,  token passing  schemes,  and
other are all worth investigating.   My main purpose is to  serve
as a catalyst for further discussion.
.
.                     What's in a Layer?
.                             or
.               Why Layer Three is not Linking
.
.                 by Lynn W. Taylor, WB6UUT
.
.  I have been reading a lot of papers recently discussing some
planned hardware,  and some "wish lists" for layer 3 (and higher)
protocols.   In  most of these,  it seems to me that the  authors
have drifted from the goal of defining what should be done at the
Communications  Subnet  level (layer 3) of  the  ISO  model.   To
explain  this level as I understand it,  I am going to present an
analogy,  discuss the issues I feel are and aren't important, and
suggest  why  layer 3 and linking should be considered  together.
Finally, I will present my layer 3 "wish list."
.
.  As   a  brief  review,   layer  1  (physical)  gives  us   a
communications  media or channel.   Our specific choices on  this
later are Radio,  HDLC,  Bell 202 and 1200 baud; it does not deal
with error rates or channel sharing.
.
.  On layer 2, we take our channel resource and split it up (in
time)  into  'virtual' channels,  and we take steps to  insure  a
(nearly)  error  free channel.   Our specific layer 2  is  AX.25,
which  defines a Local Area Net,  and provides a means to  extend
the  LAN where signal propogation is inadequate to allow the most
distant   users  to  communicate  (digipeating).    In  the   Los
Angeles/San Diego LAN,  the most distant users are over 120 miles
apart;  the user must have some knowlege of the network  topology
(who can hear whom) in order to communicate with other users.
.
.  Another  network worth considering is the telephone  system.
In this  network,  we have a physical level (baseband  audio  on
wires),  a data link layer (the local office switch),  and a good
example of a communications subnet layer.   Layer 1 is handled by
wire.   On  layer 2,  10,000 users (which share a prefix) can  be
directly connected together by switches in a single exchange.  On
layer 3, things get more complex.
.
.  While only a short distance apart, it is not possible for my
phone (497 prefix) to be connected to my parents (494 prefix); we
are  in  seperate "local networks" or local exchanges.   In  this
trivial  case  (both  exchanges are in  the  same  building),  my
exchange  selects  a  'trunk'  which connects  it  to  the  other
exchange, and then on to the call's destination.
.
.  In  the  case  of a longer call (from my  home  in  Southern
California to Pete Eaton in Saint Louis, for example), I "invoke"
a long range network (which my exchange knows how to access), and
trunks are selected connecting to various switching centers, into
Pete's exchange, and on to Pete's phone.
.
.  The  important thing to note here is that,  as far as I  can
tell, my phone can directly be connected to any phone in my local
dialing area (a geographically large LAN),  or any other phone in
the world -- without my knowing (or even being able to find  out)
which trunks,  exchanges, routing centers, etc. are involved.  In
other  words,  the task of the communications subnet layer is  to
make  it  appear  that every station in the net can  be  directly
connected to every other.
.
.  As a user in the LAN, what I should be able to do is exactly
the  same  as  when I dial my telephone -- connect to  any  other
station by simply specifying the call sign of that station.   The
connect may fail because the destination node is down,  busy,  or
simply  unreachable.   In  a seperate paper,  I have suggested  a
decentralized  mechanism  which would allow  dynamic  routing  of
packets  as the network changes -- other algorithms are possible,
including  centralized and hybrid networks.   What ever method is
finally chosen,  it should appear to the user that every  station
in the net can talk directly to every other node in the net.
.
.  Notice  that  many  of these statements are as valid  for  a
long-distance  network  (AMICON)  as for  a  local  network,  and
pehaaps  even mre valid.   It should not be necessary for me  to
specify that my data be transferred via Los Angeles,  Las  Vegas,
Salt  Lake City,  etc.  to get to Saint Louis;  especially if the
route  via  San  Diego,  Tucson,  Taos,  Houston,  etc.  is  less
congested, or if a critical node is down along the other route.
.
.  I  am  concerned  when  other issues  start  "invading"  the
communications subnet,  such as non-connect communications,  such
as sattelite (PACSAT) routing,  and mail-type services.   In the
case of message traffic,  Bulletin boards and PACSAT gateways can
provide  the necessary store-and-forward services.   In order  to
incorporate this in a protocol,  w must deal with such issues as
how to store this data (provide some nodes with lots of memory?),
how  to  access this distributed database,  and how long to  keep
these messages around.   In my opinion, this is an application of
the network best dealt with at the application level (layer 7).
.
.  In  the phone system,  special procedures are  necessary  to
access the long-range network (dialing '1').  I don't think it is
unreasonable  to  set up a gateway to a  long-haul  network,  and
require  the  user to connect to this station to  access  distant
networks.   A question here is, do I want my TNC to indicate that
I am connected to the distant station,  or is it OK or me to be
connected to the gateway itself.   A good option here might be to
connect to the linker,  give it the call I want to talk  to,  and
disconnect,  allowing  it to connect (at layer 3) to me when  the
path is established.
.
.  In other words, we want a communications subnet to be usable
without any specialized knowlege of it's topography.  In order to
reach this goal,  layer 3 is concerned with routing;  it does not
state  whether  we  are extending our  LAN,  or  linking  distant
networks.
.
.  While  these are seperate issues,  I don't think one can  be
considered without the other.  On one hand, linking LAN's is much
more  difficult  if you must give detailed  routing  information;
some  kind  of  layer  3 is almost essential  for  the  long-haul
net   On the other hand,  the LAN layer 3 would require  each
node  to  have some information about the network it's in;  if  a
long-haul gateway knows who it can reach in it's LAN,  it can  be
queried  for  a  specific station -- this query could  provide  a
"directory  assistance" function.   Using "area  codes"  suggests
that  a "packet directory" would need to be published.   A scheme
allowing  a query throughout the long-haul network  would  handle
this  case,  and  also  allow me to travel to  another  area  and
receive connects through the appropriate gateway.
.
.   Now  that I have presented some of my thoughts on the topics
of linking and layer 3,  I would like to present my "wish  list."
I would like to see a communications subnet layer running on the
TNC in the LAN,  allowing me to connect to any station in the net
by requesting a connect to that station.  I want the algorithm to
be able  to handle changing topography (due  to  stations  going
on/off line,  or changing propogation and dynamically re-route my
packets;  this does not allow for a user-specified routing, since
the  network has the authority to change the routing.   I want  a
similar  capability  to exist in the long-haul  network,  plus  a
'directory assistnce' capability allowing me to access a station
by call sign without knowing exactly where he is in the net.
.
.  I  think  this is attainable using present hardware.   As  I
discussed  in  my  previous paper ("A Proposed  Layer  3  Routing
Algorithm"),  I  feel  it  is possible to  have  dynamic  routing
in a connection environment.  The tables necessary to handle this
in the  LAN make the necessary data available to  the  long-haul
net.   This  will allow a smoothly operating local  net,  and  an
easily  accessable long-haul network which is fairly tolerant  of
failures; it should also be simple enough to implement.

[End of Article]